package com.lq.learningTest.fanxing;

public class Link<T> implements Super<T> {

    // 链表的长度
    private int size;
    // 维护一个节点
    private Node first;
    // 维护一个尾节点
    private Node last;

    public Link() {
    }

    private static class Node<T> {
        private T data;
        private Node next;

        public Node() {
        }

        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }

        public T getData() {
            return this.data;
        }

        public void setData(T data) {
            this.data = data;
        }

        public Node getNext() {
            return this.next;
        }

        public void setNext(Node next) {
            this.next = next;
        }

    }



    public int getSize() {
        return size;
    }

    public void setSize(int size) {
        this.size = size;
    }

    public Node getFirst() {
        return first;
    }

    public void setFirst(Node first) {
        this.first = first;
    }

    public Node getLast() {
        return last;
    }

    public void setLast(Node last) {
        this.last = last;
    }


    //尾插法，添加元素至链表尾部
    @Override
    public void add(T data){
        Link.Node node = new Link.Node(data,null);
        //如果链表为空链表，那么添加的节点直接为第一个节点,否则就让尾节点指向新的节点
        if (this.first == null){
            this.first = node;
        } else {
            this.last.setNext(node);
        }
        this.last = node;
        this.size ++;
    }

    //在指定下标添加元素
    @Override
    public boolean add(int index,T data){
        Node node = getNode(index);
        Link.Node newNode = new Link.Node(data,null);

        if (node != null){
            //往链表中间插入节点，新节点先指向下标节点的下一个节点地址，再把下标节点指向新节点
            newNode.setNext(node.getNext());
            node.setNext(newNode);
        } else {
            this.first = newNode;
            this.last = newNode;
        }
        this.size++;
        return true;
    }

    // 删除第一个节点
    public boolean remove(){
        if (this.size < 0){
            return false;
        }
        if (this.first != null ){
            this.first = this.first.getNext();
            this.size--;
        }
        return true;
    }

    // 删除指定元素
    @Override
    public T remove(int index){
        if (this.size < 0){
            return null;
        }
        if(this.size == 1){
            this.first = null;
            this.last = null;
        } else {
            //要删除的下标节点的前一个节点直接指向下标节点的下一个节点
            Node node = getNode(index-1);
            node.setNext(node.getNext().getNext());
        }
        this.size--;
        return get(index);
    }

    // 修改指定下标的元素
    @Override
    public boolean set(int index,T data){
        // 找到第index个
        Node node = getNode(index);
        node.setData(data);
        return true;
    }

    // 获取指定下标的元素
    @Override
    public T get(int index){
        return (T) getNode(index).getData();
    }

    //查看当前有多少个数字
    public int size(){
        return this.size;
    }

    //无头结点的单链表，输入下标返回下标对应节点的地址
    private Node getNode(int index){

        // 边界判断
        //index --;
        if(index <= 0){
            index = 1;
        }
        if(index >= this.size){
            index = this.size;
        }
        // 从第一个节点first一直getNext()直到找到第index个
        Node cursor = this.first;
        if (index==1) {
            return cursor;
        }else{
            for (int i = 1; i < index; i++) {
                cursor = cursor.getNext();
            }
        }
        return cursor;
    }
}
